home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_100 / 101_01 / stone.c < prev    next >
Encoding:
Text File  |  1985-11-13  |  9.1 KB  |  388 lines
  1.  
  2.  
  3. /*
  4.     "STONE"
  5.     (otherwise known as"Awari")
  6.  
  7.     This version written by
  8.         Terry Hayes & Clark Baker
  9.         Real-Time Systems Group
  10.         MIT Lab for Computer Science
  11.     (and hacked up a little by Leor Zolman)
  12.  
  13.     The algorithm used for STONE is a common one
  14.     to Artificial Intelligence people: the"Alpha-
  15.     Beta" pruning heuristic. By searching up and down 
  16.     a tree of possible moves and keeping record of
  17.     the minimum and maximum scores from the
  18.     terminal static evaluations, it becomes possible
  19.     to pinpoint move variations which can in no way
  20.     affect the outcome of the search. Thus, those
  21.     variations can be simply discarded, saving
  22.     expensive static evaluation time.
  23.  
  24.     To have the program print out some search
  25.     statistics for every move evaluation, type the
  26.     command as
  27.  
  28.         A> stones -d
  29.  
  30.     To also see a move-by-move trace of each terminal
  31.     evaluation, type
  32.  
  33.         A> stones -a
  34.  
  35.     THIS is the kind of program that lets C show its
  36.     stuff; Powerful expression operators and recursion
  37.     combine to let a powerful algorithm be implemented
  38.     painlessly.
  39.  
  40.     And it's fun to play!
  41.  
  42.  
  43.     Rules of the game:
  44.  
  45.     Each player has six pits in front of him and a
  46.     "home" pit on one side (the computer's home pit
  47.     is on the left; your home pit is on the right.)
  48.  
  49.     At the start of the game, all pits except the home
  50.     pits are filled with n stones, where n can be anything
  51.     from 1 to 6.
  52.  
  53.     To make a move, a player picks one of the six pits
  54.     on his side of the board that has stones in it, and
  55.     redistributes the stones one-by-one going counter-
  56.     clockwise around the board, starting with the pit
  57.     following the one picked. The opponent's HOME pit is
  58.     never deposited into.
  59.  
  60.     If the LAST stone happens to fall in that player's
  61.     home pit, he moves again.
  62.  
  63.     If the LAST stone falls into an empty pit on the
  64.     moving player's side of  board, then any stones in the
  65.     pit OPPOSITE to that go into the moving
  66.     player's home pit.
  67.  
  68.     When either player clears the six pits on his
  69.     side of the board, the game is over. The other player
  70.     takes all stones in his six pits and places them in
  71.     his home pit. Then, the player with the most stones
  72.     in his home pit is the winner.
  73.  
  74.     The six pits on the human side are numbered one
  75.     to six from left to right; the six pits on the    
  76.     computer's side are numbered one to six right-to-
  77.     left.
  78.  
  79.     The standard game seems to be with three stones;
  80.     Less stones make it somewhat easier (for both you
  81.     AND the computer), while more stones complicate
  82.     the game. As far as difficulty goes, well...it
  83.     USED to be on a scale of 1 to 50, but I couldn't
  84.     win it at level 1. So I changed it to 1-300, and
  85.     couldn't win at level 1. So I changed it to 1-1000,
  86.     and if I STILL can't win it at level 1, I think
  87.     I'm gonna commit suicide.
  88.  
  89.     Good Luck!!!
  90. */
  91.  
  92. int DEPTH, MAXDEPTH;
  93. unsigned CALLS, TOTDEPTH, WIDTH,TERM;
  94. unsigned total;
  95. int ab, db;
  96. char string[80];
  97.  
  98. unsigned COUNT;
  99. int NUM;
  100.  
  101.  
  102. main(argc,argv) int argc;
  103. char **argv;
  104. {
  105.     int  hum,com,y,inp;
  106.     char board[14];
  107.     ab = 0;
  108.     db = 0;
  109.     if (argc > 1) { inp = 0;
  110. loop:            switch(argv[1][inp++]) {
  111.             case '\0': break;
  112.             case 'D' : db++; goto loop;
  113.             case 'A' : db++; ab++; goto loop;
  114.             default:   goto loop;
  115.             }
  116.         }
  117. new:    srand1("\nDifficulty (1-1000): ");
  118.     inp = atoi(gets(string));
  119.     if (inp<1 || inp>1000) goto new;
  120.     printf("Number of stones (1-6): ");
  121.     NUM = atoi(gets(string));
  122.     COUNT = inp * 65;
  123.     initb(board);
  124.     printf("Do you want to go first (y or n)? ");
  125.     inp = toupper(getchar());
  126.     printf("\n\n");
  127.     if (inp ==  'N') goto first;
  128.     y = 0;
  129.     while(notdone(board)) {
  130.         printf("Move: ");
  131.         for (;;) {
  132.             inp = getchar() - '0';
  133.             if (toupper(inp+'0')=='Q')goto new;
  134.             if (inp < 1 || inp > 6 || !board[inp]) {
  135.                 printf("\tIllegal!!\n?");
  136.                 continue;
  137.              }
  138.             y++;
  139.             break;
  140.         }
  141.         if (!dmove(board,inp)) continue;
  142. first:
  143.         y = 0;
  144.         while (notdone(board)) {
  145.             inp = comp(board);
  146.             printf("Computer moves: ");
  147.             printf("%d\n",inp-7);
  148.             y++;
  149.             if (dmove(board,inp)) break;
  150.         }
  151.         y = 0;
  152.     }
  153.     com = board[0]; 
  154.     hum = board[7];
  155.     for (inp = 1; inp < 7; inp++) { 
  156.         hum += board[inp];
  157.         com += board[inp+7];
  158.     }
  159.     printf("Score:   me %d  you %d . . . ",com,hum);
  160.     if (com>hum) switch (rand() % 4) {
  161.         case 0: printf("Gotcha!!");
  162.             break;
  163.         case 1:    printf("Chalk one up for the good guys!");
  164.             break;
  165.         case 2: printf("Automation does it again!");
  166.             break;
  167.         case 3: printf("I LOVE to WIN!");
  168.         }
  169.     else if (hum==com) printf("How frustrating!!");
  170.     else printf("Big Deal! Try a REAL difficulty!");
  171.     putchar('\n');
  172.     printf("New Game (y or n): ");
  173.     if (toupper(getchar()) == 'Y') goto new;
  174.     exit(0);
  175. }
  176.  
  177. mmove(old,new,move) char *old;    char *new; int move;
  178. {
  179.      int i; 
  180.     int who;
  181.     total++;
  182.  
  183.     for (i = 0; i < 14; ++i) new[i] = old[i];
  184.     if ((move < 1) || (move > 13) || (move == 7) || !new[move])
  185.         printf("Bad arg to mmove: %d",move);
  186.     who = (move < 7 ? 1 : 0);
  187.     i = old[move];
  188.     new[move] = 0;
  189.     while (i--) {
  190.         move = mod(move,who);
  191.         ++new[move];
  192.     }
  193.     if (new[move] == 1 && who == (move < 7 ? 1 : 0) && move && move != 7)
  194.     {
  195.         new[who*7] += new[14-move];
  196.         new[14-move] = 0;
  197.     }
  198.     if (move == 0 || move == 7) return(0);
  199.     else return(1);
  200. }
  201.  
  202. dmove(new,move)  char *new; int move;
  203. {
  204.      int i;
  205.     int j;
  206.     int who;
  207.     i = mmove(new,new,move);
  208.     printb(new);
  209.     return(i);
  210. }
  211.  
  212. mod(i,j)  int i,j;
  213. {
  214.     ++i;
  215.     if (i == 7) return( j ? 7 : 8);
  216.     if (i > 13) return ( j ? 1 : 0);
  217.     return(i);
  218. }
  219.  
  220. initb(board)  char *board;
  221. {
  222.      int i,j;
  223.     for (i= 0; i <14; ++i) board[i] = NUM;
  224.     board[0] = board[7] = 0;
  225.     printb(board);
  226.     return;
  227. }
  228.  
  229. printb(board)  char *board;
  230. {
  231.      int i;
  232.     printf("\n ");
  233.     for (i = 13; i > 7; --i) printf("    %2d",board[i]);
  234.     printf("\n%2d                                      %2d\n",board[0],board[7]);
  235.     putchar(' ');
  236.     for (i = 1; i < 7; ++i) printf("    %2d",board[i]);
  237.     printf("\n\n");
  238. }
  239.  
  240. comp(board)  char *board;
  241. {
  242.      int score;
  243.     int bestscore,best;
  244.     char temp[14];
  245.      int i;
  246.     unsigned nodes;
  247.     DEPTH = MAXDEPTH = CALLS = TOTDEPTH = WIDTH = TERM = 0;
  248.     total = 0;
  249.  
  250.     if ((i = countnodes(board,8)) == 1)
  251.         for (best = 8; best < 14; ++best)
  252.             if (board[best]) return(best);
  253.     nodes = COUNT/i;
  254.     bestscore = -10000;
  255.     for (i = 13; i > 7; --i) if (board[i]) {
  256.         score = mmove(board,temp,i);
  257.         score = comp1( temp, score, nodes,
  258.                 db? -10000 : bestscore, 10000);
  259.         if (db) {
  260.             printf("MOVE: %2d    SCORE: %5d",
  261.                 i-7,
  262.              (score>=1000)?(score-1000):
  263.               ((score<= -1000)?(score+1000):score));
  264.             if (score > 1000 || score < -1000) printf("  for SURE");
  265.             printf("\n");
  266.         }
  267.  
  268.         if (score > bestscore) {
  269.             bestscore = score;
  270.             best = i;
  271.         }
  272.     }
  273.     if (bestscore > 1000)
  274.         printf("I'VE GOT YOU!\n"); 
  275.     if (bestscore < -1000)
  276.         printf("YOU'VE GOT ME!\n");
  277.     if (db) {
  278.         printf("\nCount: %u\n",total);
  279.         printf("Maximum depth: %d\nAverage depth: %u\n",
  280.         MAXDEPTH,TOTDEPTH/CALLS);
  281.         printf("Terminal Evaluations: %u\nPlayed out: %u\n",WIDTH,TERM);
  282.     }
  283.  
  284.     return(best);
  285. }
  286.  
  287. comp1(board,who,count,alpha,beta)
  288.  char *board; int who; int alpha,beta;
  289. unsigned count; 
  290. {
  291.      int i;
  292.     int turn,new;
  293.     char temp[14];
  294.     unsigned nodes;
  295.     ++DEPTH;
  296.     MAXDEPTH = max(MAXDEPTH,DEPTH); 
  297.  
  298.     if (count < 1) {
  299.         ++CALLS;
  300.         TOTDEPTH += DEPTH;
  301.         ++WIDTH;
  302.         --DEPTH;
  303.  
  304.         new = board[0]-board[7];
  305.         for (i = 1; i < 7; ++i) { turn = min(7-i,board[i]);
  306.                       new -= 2*turn - board[i]; }
  307.         for (i = 8; i < 14; ++i) { turn = min(14-i,board[i]);
  308.                        new += 2*turn - board[i]; }
  309.         if (board[0] > 6*NUM) new += 1000;
  310.         if (board[7] > 6*NUM) new -= 1000;
  311.         return(new);
  312.     }
  313.     if (!notdone(board)) {
  314.         ++CALLS;
  315.         TOTDEPTH += DEPTH;
  316.         ++TERM;
  317.         --DEPTH;
  318.  
  319.         new = board[0]+board[8]+board[9]+board[10]
  320.             +board[11]+board[12]+board[13]-board[1]-board[2]
  321.             -board[3]-board[4]-board[5]-board[6]-board[7];
  322.         if ( new < 0) return (new - 1000);
  323.         if ( new > 0) return (new + 1000);
  324.         return(0);
  325.     }
  326.     nodes = count/countnodes(board,8-who*7);
  327.     for (i = 7*(1-who)+6; i > 7*(1-who); --i)
  328.         if (board[i]) {
  329.             turn = mmove(board,temp,i);
  330.             new = comp1(temp,(turn ? 1-who : who),nodes,alpha,beta);
  331.             if (ab) printf("DEPTH: %2d  MOVE: %2d  NEW: %4d  ALPHA: %6d  BETA: %6d\n",DEPTH,i,new,alpha,beta);
  332.             if (who) {
  333.                beta = min(new,beta);
  334.                if (beta <= alpha) { DEPTH--; return(beta); }}
  335.             else {
  336.                 alpha = max(new,alpha);
  337.                 if (alpha >= beta) { DEPTH--; return(alpha); }}
  338.         }
  339.     --DEPTH;
  340.  
  341.     return(who ? beta : alpha);
  342. }
  343.  
  344. min(i,j)  int i,j;
  345. {
  346.     return(i < j ? i : j);
  347. }
  348.  
  349. max(i,j)  int i,j;
  350. {
  351.     return(i > j ? i : j);
  352. }
  353.  
  354. notdone(board)    char *board;
  355. {
  356.     return (board[1] || board[2] || board[3] || board[4]
  357.         || board[5] || board[6]) &&
  358.            (board[8] || board[9] || board[10] || board[11]
  359.         || board[12] || board[13]);
  360. }
  361.  
  362. countnodes(board,start) int start; char *board; 
  363. {
  364.     int i;
  365.     int num;
  366.     num = 0;
  367.     for (i = start; i< start + 6; ++i)
  368.         num += (board[i] ? 1 : 0);
  369.     return(num);
  370. }
  371.  
  372. rd; 
  373. {
  374.     int i;
  375.     int num;
  376.     num = 0;
  377.     for (i = start; i< start + 6; ++i)
  378. continue;
  379.         oside |= 1;
  380.         s -= dkl;
  381.         if (c>=10) { s -= 4; oside |= 8; }
  382.         }
  383.     if (s< -oside) s= -oside;
  384.     if (side>0) return s+side-7+10*ok;
  385.     if (i==1 || i==6) {s--; side++;}
  386.     if (j==1 || j==6) {s--; side++;}
  387.     if (side>0) return s;
  388.     if (i==2 || i=